#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef struct BSTNode {
    KeyType key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

//采用递归的方式
int BST_Insert_Recursion(BSTree &tree, KeyType data) {
    if (tree == NULL) {
        tree = (BSTree) calloc(1, sizeof(BSTNode));
        tree->key = data;
        return 1;
    } else if (tree->key > data) {
        return BST_Insert_Recursion(tree->lchild, data);
    } else if (tree->key == data) {
        return 0;
    } else {
        return BST_Insert_Recursion(tree->rchild, data);
    }
}

void Create_BST(BSTree &tree, KeyType *str, KeyType len) {
    for (int i = 0; i < len; ++i) {
        scanf("%d", &str[i]);
    }
    for (int i = 0; i < len; ++i) {
        BST_Insert_Recursion(tree, str[i]);
    }
}

//中序排序
void InOrder(BSTree tree) {
    if (tree) {
        InOrder(tree->lchild);
        printf("%3d", tree->key);
        InOrder(tree->rchild);
    }
}

int compare(const void *left, const void *right) {
    return *(int *) (left) - *(int *) (right);
}

int main() {
    BSTree tree = NULL;
    KeyType str[10];
    Create_BST(tree, str, 10);
    InOrder(tree);
    qsort(str, 10, sizeof(KeyType), compare);
    //仅以测试
//    printf("\n");
//    for (int i:str) {
//        printf("%2d ",i);
//    }
    KeyType low, high, pos = -1;
    low = 0;
    high = 9;
    while (low <= high) {
        KeyType mid = (low + high) / 2;
        if (str[mid] == 21) {
            pos = mid;
            break;
        } else if (str[mid] > 21) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    printf("\n");
    if (pos != -1) {
        printf("%d", pos);
    }
    return 0;
}


